package cn.fansunion.leecode.linkedlist;

/**
 * 21. 合并两个有序链表 <br/>将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-2-18
 */
public class MergeTwoSortedLists {
    /* 输入：l1 = [1,2,4], l2 = [1,3,4]
        输出：[1,1,2,3,4,4]
        示例 2：
    
        输入：l1 = [], l2 = []
        输出：[]
        示例 3：
    
        输入：l1 = [], l2 = [0]
        输出：[0]
    */
    // l1 和 l2 均按 非递减顺序 排列
    /**
     * 同MergeSortedArray的思路一样，代码结构基本一样。由于链表和数组的特点不同，语法方法上有所差异，核心不同点：4行代码。
     * 
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 虚拟1个头结点，方便操作
        ListNode head = new ListNode();
        ListNode cur = head;
        while (list1 != null && list2 != null) {
            int val1 = list1.val;
            int val2 = list2.val;
            if (val1 <= val2) {
                // 记录当前节点的下一个节点
                ListNode next1 = list1.next;
                // 全局当前节点
                cur.next = list1;
                // 遍历下一个节点
                list1 = next1;
                cur = cur.next;
            } else {
                // 记录当前节点的下一个节点
                ListNode next2 = list2.next;
                // 全局当前节点
                cur.next = list2;
                // 遍历下一个节点
                list2 = next2;
                cur = cur.next;
            }
        }
        //todo:可以优化 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        // list1有剩余的
        while (list1 != null) {
            //务必先临时记录下一个节点，有点“swap交换的味道”
            ListNode next1 = list1.next;
            cur.next = list1;
            list1 = next1;
            cur = cur.next;
        }
        // list2有剩余的
        while (list2 != null) {
            ListNode next2 = list2.next;
            cur.next = list2;
            list2 = next2;
            cur = cur.next;
        }
        return head.next;

    }
}
